import { Compare, defaultCompare } from '../../util';

/**
 * 与冒泡和选择两种排序不同的是，插入排序(insertion-sort)不会从剩余项中找最大或最小项
 * 放入数组一端，它是每轮从剩余项中随意取一项（默认取第一个），将它与排好序的项进行比较，
 * 然后放入适当的位置；一直到剩余项都处理完。
 * @param array 目标数组
 * @param compareFn 比较函数
 * 可以说插入排序是反其道而行，随意从剩余项中取一项然后按顺序插入已排序列表里，例如插扑克牌。
 * 最差、平均时间复杂度是O(n^2)，最好情况是O(n)；空间复杂度是O(1)。
 */
export const insertionSort = (array: any[], compareFn = defaultCompare) => {
    // 数组长度
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    /*
        每轮取剩余项的第一个放入已排序列表里；
        初始化时，有序列表就一项，即i=0那项，那么剩余项从i=1开始;
        后面就是有序列表有两项，那么剩余项是从索引2开始的......
    */
    for (let i = 1; i < length; i ++) {
        // 当前项temp，即将插入已排序列表中
        const temp = array[i];
        // 当前项的前一项，是已排序列表的最左侧项并且是最大的一项
        let j = i - 1;
        /*
            temp比已排序列表的最大项还大或相等，temp不用插入了直接下一轮
            这是插入排序最佳时间复杂度为O(N)的原因，其他情况都是O(N^2)
        */
        if (compareFn(temp, array[j]) !== Compare.LESS_THAN) {
            continue;
        }
        // 从有序列表的左边往右遍历，temp更小可以插入，那么array[j]需要左挪腾出位置
        while (j >= 0 && compareFn(temp, array[j]) === Compare.LESS_THAN) {
            // array[j]往左挪，挪到j + 1
            array[j + 1] = array[j];
            // 从有序列表的左边往右遍历，j要自减
            j --;
        }
        // 最后空出的位置，将temp插到空位
        array[j + 1] = temp;
    }
    return array;
};
